#define SVD
using System;
using System.Globalization;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Windows;
using System.Windows.Controls;
using System.Windows.Documents;
using System.Windows.Media;
using System.Windows.Shapes;
using System.ComponentModel;
using glue.Extensions.Enumerable;
using glue.XDag;
using Matrix = glue.Math.Matrix.Matrix;
namespace glue.WpfUtil
{
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// <summary>
///
/// </summary>
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
public partial class DagLayoutPanel : Panel
{
class LayoutDag : Dag<LayoutDag.Node>
{
static Size infinite_size = new Size(double.PositiveInfinity, double.PositiveInfinity);
[DebuggerDisplay("{ToString(),nq}")]
public new class Node : Dag<LayoutDag.Node>.Node, INotifyPropertyChanged
{
[DebuggerBrowsable(DebuggerBrowsableState.Never)]
Point top_handle;
[DebuggerBrowsable(DebuggerBrowsableState.Never)]
Point bot_handle;
//[DebuggerBrowsable(DebuggerBrowsableState.Never)]
Rect r_cur;
[DebuggerBrowsable(DebuggerBrowsableState.Never)]
readonly public FrameworkElement fe;
public int order;
static int i_next = 0;
public enum LayoutMode
{
Fixed = 0,
ArrangeToParents = 1,
ArrangeToChildren = 2,
}
public Node(LayoutDag ld, FrameworkElement fe)
: base(ld)
{
this.order = i_next++;
this.fe = fe;
fe.Measure(infinite_size);
}
public void SetFixedLayout(Point pt)
{
r_cur = new Rect(pt, DesiredSize);
}
public void PrepareLayout()
{
if (Parents.Count > 0)
{
foreach (Node par in Parents)
par.PropertyChanged += new PropertyChangedEventHandler(ParentPropertyChanged);
}
if (Children.Count > 0)
{
foreach (Node n in Children)
n.PropertyChanged += new PropertyChangedEventHandler(ChildPropertyChanged);
}
}
public void UpdateLayout()
{
if (Children.Count > 0 && Children.All(c => c.Parents.Count == 1))
{
foreach (Node n in Children)
n.CurrentLayout = GetChildProposal(n);
}
else if (Parents.Count > 0 && Parents.All(c => c.Children.Count == 1))
{
foreach (Node n in Parents)
n.CurrentLayout = GetParentProposal(n);
}
else
{
}
}
Rect[] child_proposals = null;
Rect[] ChildProposals
{
get
{
if (child_proposals == null)
{
Node[] rg = OrderedChildren.ToArray();
child_proposals = new Rect[rg.Length];
double dx = 0;
int i = 0;
foreach (Node c in rg)
{
// if (c.Level == Level + 1)
{
if (dx > 0)
dx += 10;
Rect cp = new Rect(new Point(dx, c.Level * 70), c.DesiredSize);
child_proposals[i] = cp;
dx += cp.Width;
}
i++;
}
double w = r_cur.Left + (r_cur.Width / 2) - (dx / 2);
i = 0;
foreach (Node c in rg)
{
// if (c.Level == Level + 1)
child_proposals[i].X += w;
i++;
}
}
return child_proposals;
}
}
Rect GetChildProposal(Node child)
{
Debug.Assert(Children.Count > 0);
return ChildProposals[GetChildIndex(child)];
}
Rect[] parent_proposals = null;
Rect[] ParentProposals
{
get
{
if (parent_proposals == null)
{
Node[] rg = OrderedParents.ToArray();
parent_proposals = new Rect[rg.Length];
double dx = 0;
int i = 0;
foreach (Node p in rg)
{
// if (p.Level == Level - 1)
{
if (dx > 0)
dx += 10;
Rect cp = new Rect(new Point(dx, p.Level * 70), p.DesiredSize);
parent_proposals[i] = cp;
dx += cp.Width;
}
i++;
}
double w = r_cur.Left + ((r_cur.Width / 2) - (dx / 2));
i = 0;
foreach (Node p in rg)
{
// if (p.Level == Level - 1)
parent_proposals[i].X += w;
i++;
}
}
return parent_proposals;
}
}
Rect GetParentProposal(Node parent)
{
Debug.Assert(Parents.Count > 0);
return ParentProposals[GetParentIndex(parent)];
}
IEnumerable<Node> OrderedChildren
{
get { return Children.OrderBy(n => n.order); }
}
IEnumerable<Node> OrderedParents
{
get { return Parents.OrderBy(n => n.order); }
}
int GetChildIndex(Node child)
{
return OrderedChildren.IndexOfFirst(n => n == child);
}
int GetParentIndex(Node parent)
{
return OrderedParents.IndexOfFirst(n => n == parent);
}
public Rect CurrentLayout
{
get
{
return r_cur;
}
set
{
if (f_changing_property)
return;
if (!value.Equals(r_cur) && !value.Equals(default(Rect)))
{
r_cur = value;
child_proposals = null;
parent_proposals = null;
NotifyPropertyChanged("CurrentLayout");
}
}
}
//double par_min;
//double par_max;
void ParentPropertyChanged(object sender, PropertyChangedEventArgs e)
{
if (!f_changing_property && e.PropertyName == "CurrentLayout")
{
Node parent = (Node)sender;
//CurrentLayout = parent.GetChildProposal(this);
UpdateLayout();
}
}
void ChildPropertyChanged(object sender, PropertyChangedEventArgs e)
{
if (!f_changing_property && e.PropertyName == "CurrentLayout")
{
Node child = (Node)sender;
//CurrentLayout = child.GetParentProposal(this);
UpdateLayout();
}
}
public Size DesiredSize { get { return fe.DesiredSize; } }
public FrameworkElement Item { get { return fe; } }
public Rect Final
{
get
{
Rect r_final;
Size desired = DesiredSize;
r_final = r_cur;
top_handle = r_final.TopLeft;
top_handle.X += r_final.Width / 2;
bot_handle = r_final.BottomLeft;
bot_handle.X += r_final.Width / 2;
return r_final;
}
}
public void DoRender(DrawingContext dc, Pen pen, Pen dashpen)
{
foreach (var cn in Children)
{
if (!cn.top_handle.Equals(default(Point)))
dc.DrawLine(pen, bot_handle, cn.top_handle);
}
}
public new LayoutDag Dag { get { return (LayoutDag)base.Dag; } }
public override string ToString()
{
return String.Format("{0} {1} parents: {2} children: {3}", fe.Name, Parents.Count, Children.Count);
}
bool f_changing_property = false;
void NotifyPropertyChanged(String s_field)
{
var h = PropertyChanged;
if (h != null)
{
f_changing_property = true;
h(this, new PropertyChangedEventArgs(s_field));
f_changing_property = false;
}
}
public event PropertyChangedEventHandler PropertyChanged;
};
};
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#if false
protected override void OnVisualChildrenChanged(DependencyObject visualAdded, DependencyObject visualRemoved)
{
base.OnVisualChildrenChanged(visualAdded, visualRemoved);
FrameworkElement node = visualAdded as FrameworkElement;
if (node != null)
{
dag2.AddNode(node);
IList parents = node.GetValue(DagParentsProperty) as IList;
if (parents != null)
foreach (FrameworkElement parent in parents.OfType<FrameworkElement>())
dag2.AddParent(node, parent);
if (node.Visibility == Visibility.Hidden)
{
dag2.SetNodeCollapsed(node, true);
}
}
node = visualRemoved as FrameworkElement;
if (node != null)
{
foreach (FrameworkElement p in dag2.Parents(node))
dag2.RemoveParent(node, p);
foreach (FrameworkElement c in dag2.Children(node))
dag2.RemoveChild(node, c);
///...
///delete node
}
}
#endif
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
protected override void OnChildDesiredSizeChanged(UIElement child)
{
base.OnChildDesiredSizeChanged(child);
}
static IEnumerable<FrameworkElement> VisibleParents(FrameworkElement node)
{
HashSet<FrameworkElement> hs = new HashSet<FrameworkElement>();
GetVisibleParents(hs, node);
return hs;
}
static void GetVisibleParents(HashSet<FrameworkElement> found, FrameworkElement node)
{
IList parents = node.GetValue(DagParentsProperty) as IList;
if (parents == null)
return;
foreach (FrameworkElement parent in parents.OfType<FrameworkElement>())
{
if (parent.Visibility == Visibility.Hidden)
GetVisibleParents(found, parent);
else
found.Add(parent);
}
}
Double y_spacing = 70;
LayoutDag dag;
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
protected override Size MeasureOverride(Size availableSize)
{
FrameworkElement[] children = InternalChildren
.OfType<FrameworkElement>()
.Where(fe => fe.Visibility == Visibility.Visible)
.ToArray();
if (children.Length == 0)
return new Size(100, 100);
dag = new LayoutDag();
Dictionary<FrameworkElement, LayoutDag.Node> layouts = new Dictionary<FrameworkElement, LayoutDag.Node>();
foreach (var fe in children)
{
LayoutDag.Node ln = new LayoutDag.Node(dag, fe);
layouts.Add(fe, ln);
}
foreach (var kvp in layouts)
{
FrameworkElement fe = kvp.Key;
LayoutDag.Node node = kvp.Value;
foreach (FrameworkElement fe_par in VisibleParents(fe))
{
LayoutDag.Node n_par = layouts[fe_par];
node.AddParent(n_par);
}
}
#if false
// var tn = dag
// .Where(n => n.Parents.Count == 1 && n.Children.Count > 0 && n.Children.All(ch => ch.IsLeaf))
// .ToArray();
// Debug.Print("removing {0} children from {1} nodes", tn.Sum(n => n.Children.Count), tn.Length);
List<LayoutDag.Node> to_remove = new List<LayoutDag.Node>();
foreach (var zzz in dag)
{
foreach (var xyz in zzz.Children)
{
if (xyz.IsLeaf && xyz.Parents.Count == 1)
{
zzz.leaves.Add(xyz.Item);
to_remove.Add(xyz);
}
}
}
Debug.Print("removing {0} child nodes", to_remove.Count);
foreach (var rn in to_remove)
dag.Remove(rn);
#endif
double x = 0;
#if SVD
DagLayoutCalc dlc = new DagLayoutCalc(this);
dlc.ComputeSingularValueDecomposition(1);
double[] lx = dlc.B.Row(0);
int j = 0;
foreach (int i in lx.Select((v, ix) => new { v, ix }).OrderBy(a => a.v).Select(a => a.ix))
{
dag[i].order = j++;
}
LayoutDag.Node[][] level_nodes = lx.Select((v, ix) => new { v, node = dag[ix] })
.GroupBy(a => a.node.Level)
.OrderBy(g => g.Key)
.Select(g => g.OrderBy(a => a.v).Select(a => a.node).ToArray())
.ToArray();
int lv_most = level_nodes.IndexOfMax(rg => rg.Length);
foreach (var lix in level_nodes)
{
// if (li.Level == lv_most)
x = 0;
foreach (var li in lix)
{
//li.Final = ;
li.SetFixedLayout(new Point(x, li.Level * y_spacing));
x += (int)li.DesiredSize.Width + 10;
}
//else if (li.Children.Count == 0)
//{
// //li.lm = LayoutDag.Node.LayoutMode.ArrangeToParents;
//}
//else if (li.Parents.Count == 0)
//{
// //li.lm = LayoutDag.Node.LayoutMode.ArrangeToChildren;
//}
//else if (li.Children.All(ch => ch.Parents.Count == 1))
//{
// li.lm = LayoutDag.Node.LayoutMode.ArrangeToChildren;
//}
//else if (li.Parents.All(p => Children.Count == 1))
//{
// li.lm = LayoutDag.Node.LayoutMode.ArrangeToParents;
//}
//else if (li.Level < lv_most)
//{
// li.lm = LayoutDag.Node.LayoutMode.ArrangeToChildren;
//}
//else if (li.Level > lv_most)
//{
// li.lm = LayoutDag.Node.LayoutMode.ArrangeToParents;
//}
}
#else
int[] level_x = new int[dag.MaxLevel + 1];
foreach (var li in dag)
{
Size desired = li.DesiredSize;
x = level_x[li.Level];
if (x > 0)
x += 10;
li.SetFixedLayout(new Point(x, li.Level * y_spacing));
level_x[li.Level] = (int)li.Final.Right;
}
#endif
foreach (var n in dag)
{
n.PrepareLayout();
}
foreach (var n in dag)
{
n.UpdateLayout();
}
#if SVD
#if false
int lv_cur = lv_most;
bool f_any;
do
{
f_any = false;
while (--lv_cur >= 0)
{
foreach (var li in level_nodes[lv_cur].Where(n => n.Final.Equals(default(Rect))))
{
Size desired = li.DesiredSize;
LayoutDag.Node[] rgnln;
if (li.lm == LayoutDag.Node.LayoutMode.ArrangeToChildren)
rgnln = li.Children.ToArray();
else
rgnln = li.Parents.ToArray();
if (rgnln.Length > 0)
{
double x0 = rgnln.Min(nln => nln.Final.Left);
double x1 = rgnln.Max(nln => nln.Final.Right);
x = x0 + ((x1 - x0) / 2 - desired.Width / 2);
if (x > 0)
{
li.Final = new Rect(new Point(x, li.Level * y_spacing), desired);
f_any = true;
}
else
{
glue.Debugging.Nop.X();
}
}
}
}
lv_cur = dag.MaxLevel + 1;
}
while (f_any);
#endif
#if false
int lv_cur = lv_most;
while (--lv_cur >= 0)
{
foreach (var li in level_nodes[lv_cur].Where(n => n.lm == LayoutDag.Node.LayoutMode.ArrangeToChildren))
{
Size desired = li.DesiredSize;
var rgnln = li.Children.ToArray();
if (rgnln.Length > 0)
{
double x0 = rgnln.Min(nln => nln.Final.Left);
double x1 = rgnln.Max(nln => nln.Final.Right);
x = x0 + ((x1 - x0) / 2 - desired.Width / 2);
li.Final = new Rect(new Point(x, li.Level * y_spacing), desired);
}
else
Debugger.Break();
}
}
while (++lv_cur < lv_most)
{
foreach (var li in level_nodes[lv_cur].Where(n => n.lm == LayoutDag.Node.LayoutMode.ArrangeToParents))
{
Size desired = li.DesiredSize;
var rgnln = li.Parents.ToArray();
if (rgnln.Length > 0)
{
double x0 = rgnln.Min(nln => nln.Final.Left);
double x1 = rgnln.Max(nln => nln.Final.Right);
x = x0 + ((x1 - x0) / 2 - desired.Width / 2);
li.Final = new Rect(new Point(x, li.Level * y_spacing), desired);
}
else
Debugger.Break();
}
}
while (++lv_cur <= dag.MaxLevel)
{
foreach (var li in level_nodes[lv_cur].Where(n => n.lm == LayoutDag.Node.LayoutMode.ArrangeToParents))
{
Size desired = li.DesiredSize;
var rgpln = li.Parents.ToArray();
if (rgpln.Length > 0)
{
double x0 = rgpln.Min(nln => nln.Final.Left);
double x1 = rgpln.Max(nln => nln.Final.Right);
x = x0 + ((x1 - x0) / 2 - desired.Width / 2);
li.Final = new Rect(new Point(x, li.Level * y_spacing), desired);
}
else
Debugger.Break();
}
}
while (--lv_cur > lv_most)
{
foreach (var li in level_nodes[lv_cur].Where(n => n.lm == LayoutDag.Node.LayoutMode.ArrangeToChildren))
{
Size desired = li.DesiredSize;
var rgpln = li.Children.ToArray();
if (rgpln.Length > 0)
{
double x0 = rgpln.Min(nln => nln.Final.Left);
double x1 = rgpln.Max(nln => nln.Final.Right);
x = x0 + ((x1 - x0) / 2 - desired.Width / 2);
li.Final = new Rect(new Point(x, li.Level * y_spacing), desired);
}
else
Debugger.Break();
}
}
#endif
#endif
double x_min = dag.Min(n => n.Final.Left);
double x_max = dag.Max(n => n.Final.Right);
double y_min = 0;
double y_max = dag.Max(n => n.Final.Bottom);
//foreach (var li in dag)
//{
// if (li.Final.Right > x_max)
// x_max = li.Final.Right;
// if (li.Final.Bottom > y_max)
// y_max = li.Final.Bottom;
//}
RenderTransform = new TranslateTransform(-x_min, 0);
return new Size(x_max - x_min, y_max);
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
protected override Size ArrangeOverride(Size finalSize)
{
if (dag == null)
return new Size(100, 100);
foreach (var li in dag)
{
li.Item.Arrange(li.Final);
}
return finalSize;
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
protected override void OnRender(DrawingContext dc)
{
base.OnRender(dc);
if (dag == null)
return;
Pen pen = new Pen(Stroke, StrokeThickness);
Pen dashpen = new Pen(Stroke, StrokeThickness);
dashpen.DashStyle = DashStyles.Dash;
foreach (var li in dag)
{
li.DoRender(dc, pen, dashpen);
}
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
class DagLayoutCalc
{
DagLayoutPanel panel;
public Matrix B;
public DagLayoutCalc(DagLayoutPanel panel)
{
this.panel = panel;
}
public void ComputeSingularValueDecomposition(int n_reduce_dims)
{
Matrix A = new double[panel.dag.Count, panel.dag.Count];
int i = 0;
foreach (var node in panel.dag)
{
double[] v = new double[panel.dag.Count];
foreach (var pnode in node.Parents)
{
v[pnode.Index] = 1;// panel.dag.MaxLevel - (li.level - li2.level);
}
v[node.Index] = 2;// panel.dag.MaxLevel;
foreach (var cnode in node.Children)
{
v[cnode.Index] = 1;// panel.dag.MaxLevel - (li2.level - li.level);
}
A.SetColumnValues(i, v);
i++;
}
Debug.Print("Starting Singular Value Decomposition for matrix A[{0},{1}]", A.RowCount, A.ColumnCount);
Stopwatch stopwatch = Stopwatch.StartNew();
double[] w;
Matrix VV;
{
Matrix V;
Matrix.SingularValueDecomposition(A, out w, out V);
Debug.Print("SVD complete in {0} ms.", stopwatch.Elapsed.TotalMilliseconds);
VV = n_reduce_dims < V.RowCount ? V.TakeKRows(n_reduce_dims) : V;
}
/// populate w (the singular values) to the diagonal of a new square matrix and multiply by the first n rows of V.
B = new Matrix(w, n_reduce_dims) * VV;
Debug.Print("Dimensionality reduction to B[{0},{1}] complete.", B.RowCount, B.ColumnCount);
}
};
};
}